The ability to create and verify timestamps on documents is important for many business functions, since parties often need to be able to convince others as to when documents were created and that documents have not been altered. The traditional solution to this problem is to use a notary public, but traditional notarization is time-consuming, requires the physical presence of a licensed notary, does not detect many kinds of document tampering, and provides security which relies solely on the integrity of the notary.
There are alternate ways to timestamp documents known in the background art. For example, the employee time card recorder of U.S. Pat. No. 3,638,233 to Futter allows the user to timestamp pieces of paper (e.g., timecards). However this type of apparatus is not secure enough for many timestamping applications. Specifically, the timestamp is not cryptographically bound to the contents of the document, so dishonest users can modify stamped documents or stamp blank pages to write on later. As with the notary, there is no assurance of the integrity of the information contained in the timestamped document.
Techniques for timestamping digital data are also known in the background art. Many such techniques, including those of U.S. Pat. Nos. 5,001,752 and 5,422,953 to Fischer and U.S. Pat. No. 5,189,700 to Blandford, rely on customized, tamper-resistant hardware. Such tamper-resistant hardware systems are extremely difficult to design, expensive to manufacture, and are often broken by attackers. Furthermore, because these systems are designed to work only with electronic data, while most business documents are on paper, they have not found widespread acceptance in commercial settings.
Other approaches known in the background art require that users submit digital data to timestamp (or a cryptographic hash of the data) to a centralized, trusted timestamping service. In "Cryptography and Data Security," Addison Wesley (1983), p. 165, Dorothy Denning describes a similar timestamping technique in which a trusted service combines the user's data with the digital representation of the date and time, then digitally signs the result using a digital signature function such as the RSA algorithm of U.S. Pat. No. 4,405,829 to Rivest et al. To verify that the data and timestamp have not been altered or forged, one uses the timestamp service's public key to check the digital signature. The technique is described by Denning is designed to allow verification of data signed by A even if A's signing key is later compromised. The timestamping service S receives the data to timestamp, typically D.sub.A (M) (the message M digitally signed by A, using digital signature algorithm D). S then combines D.sub.A (M) with the time T and digitally signs the result, returning C=D.sub.S (D.sub.A (M), T). Anyone with the public key for S, knowledge of the timestamped message D.sub.A (M), the time T, and digital signature C can verify the signature to confirm that, according to S, the message D.sub.A (M) was timestamped at time T.
Other digital data timestamping service designs are known in the background art. For example, techniques using catenate certificates and hash trees as described in U.S. Pat. Nos. 5,136,646 and 5,136,647 (now U.S. Pat No. Re 34,954), both to Haber et al., provide roughly similar functionality as the system described by Denning and can help to prevent the timestamping service from acting dishonestly. U.S. Pat. No. 5,022,080 to Durst also describes a timestamping apparatus and method for electronic notarization. A significant problem with these timestamping systems is that timestamp verification requires knowledge of the exact message signed (e.g., D.sub.A (M) and T), which users are responsible for archiving.
Although existing digital timestamping service designs can provide acceptable security against tampering and forgery of digital data, they are not well suited to the world of paper documents. Specifically, they either fail to disclose techniques for dealing with paper documents, or disclose techniques that are too complicated or too expensive for widespread acceptance. Furthermore, verification of a digital timestamp requires knowledge of the exact data which were timestamped. Scanning a paper document twice tends to produce slightly different results; thus, the digitized image produced during the verification process will often not match the timestamped version, causing verification to fail unless users archive the actual digital data which was timestamped. Finally, because specialized apparatuses are required to create timestamps and perform the verification, existing digital timestamps are useless to people who lack such hardware or software.
A different, but also important, problem is providing proof of transmission and proof of receipt for telecopier transmissions. In particular, including when using the timestamping service of the present invention, telecopier and facsimile users may require confirmation that their transmissions were received and processed successfully. Although standard facsimile protocols allow the recipient to report transmission errors, such acknowledgment does not guarantee that the entire transmission process was successful. For example, the recipient's facsimile may report success even if its printer runs out of ink and thus produces unreadable output pages.
U.S. Pat. No. 5,432,618 to Monnot et al describes a technique by which, if both parties have specially-equipped hardware devices, successful transmission can be confirmed for a small block of specially-formatted summary text at the beginning of the transmission. Although U.S. Pat. No. 5,432,618 can provide authentication for the benefit of the receiver of a transmission, the sender is not assured that the recipient obtained a complete and legible copy of the document. Also, only a small fraction of the information contained in the document is confirmed: additional complicated user interactions are required to generate the summary data to confirm; complicated optical character recognition technology is required; and users must have specialized hardware (e.g., a smart-card and a specially-equipped facsimile machine).
U.S. Pat. No. 5,377,017 to Lam describes a means of providing return receipt capabilities for facsimile in which the complete pages transmitted, or a portion thereof (i.e., the top third of the first page and the bottom third of the last page) are returned to the sender. However, the receipt is either incomplete (providing no assurance for non-confirmed portions) or is as long as the entire document. Also, Lam's receipt is generated from the transmission while it is still in electronic form, and does not guarantee that the recipient's facsimile actually printed the transmission legibly.
U.S. Pat. No. 4,779,106 to Mills, U.S. Pat. No. 4,849,821 to Allen et at., and U.S. Pat. No. 4,545,031 Kobayashi describe techniques for scanning the output pages from photocopiers or printers, and comparing the results against reference pages to detect errors.
U.S. Pat. No. 5,566,230 to Cairo describes an apparatus which can be integrated with a telephone switch to monitor facsimile transmissions and print an additional copy, which can be certified and sent via registered mail to the sender. However the delay imposed by the mailing of the certified copy is a significant problem for senders who require immediate confirmation. Specialized equipment must also be installed at the telephone switch, making the system difficult to implement. The system is also expensive to operate, since paper printouts must be produced, certified, and mailed. Finally, although the sender's transmission is certified, there is still no guarantee that the recipient's facsimile machine produced a complete and legible printout of the document.
The foregoing shows that there exists a need for a timestamping system that is suitable for use with paper documents, yet provides cryptographically-assured verification, and which is accessible to users with no modification to their existing document transmission devices (e.g., facsimile machines).